package cn.threecubic.sort;

import java.util.Arrays;

/**
 * 快速排序
 *
 * @author Terminator
 * @date 2021/10/21 9:16
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] data = {14, 33, 27, 10, 35, 19, 42, 44};
        System.out.println("快速排序,排序前：" + Arrays.toString(data));
        quickSort(data, 0, data.length - 1);
        System.out.println("快速排序,排序后：" + Arrays.toString(data));
    }

    /**
     * 快速排序
     *
     * @param arr
     * @param left
     * @param right
     */
    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            // 整理位置并得到划分位置
            int partitionIndex = partition(arr, left, right);
            quickSort(arr, left, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, right);
        }
    }

    /**
     * 划分（小的在左边，大的在右边）
     *
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public static int partition(int[] arr, int left, int right) {
        // 基准元素
        int temp = arr[left];
        // 循环至左右指针重合
        while (left < right) {
            // 从右开始找到比基准元素小的元素，并覆盖到左指针元素
            while (left < right && arr[right] >= temp) {
                right--;
            }
            arr[left] = arr[right];
            // 从左开始找到比基准元素大的元素，并覆盖到右指针元素
            while (left < right && arr[left] <= temp) {
                left++;
            }
            arr[right] = arr[left];
        }
        // 左右指针重合位置存放基准元素，并作为划分位置返回
        arr[left] = temp;
        return left;
    }

}
